// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"fmt"
	"strings"
)

type SparseTreeNode struct {
	child   *Block
	sibling *Block
	parent  *Block

	// 每个块都有6个与之关联的数字：
	// 入口1，入口，入口+1，出口-1，出口+1。
	// 入口和出口在概念上是块的顶部（phi函数）
	// 入口+1和出口-1在概念上是块的底部（普通DEF）
	// 入口-1和出口+1在概念上“就在”区块之前（条件流入）
	// None
	// 如果我们想查询有关x的信息，这将简化我们的生活
	// 当x既是块的输入又是块的输出时。
	entry, exit int32
}

func (s *SparseTreeNode) String() string {
	return fmt.Sprintf("[%d,%d]", s.entry, s.exit)
}

func (s *SparseTreeNode) Entry() int32 {
	return s.entry
}

func (s *SparseTreeNode) Exit() int32 {
	return s.exit
}

const (
	// 用于在稀疏树中查找定义时，
	// 对块条目的这些调整（+调整）和
	// 出口（-adjust）数字允许进行区分
	// 分配之间（通常取决于分支）
	// 条件）出现在块之前（例如，作为输入
	// 到块及其phi函数），在块内，
	// “在”街区之后。
	AdjustBefore = -1 // 在φ之前定义
	AdjustWithin = 0  // 由phi定义
	AdjustAfter  = 1  // 在块内定义
)

// 稀疏树是由块组成的树。
// 它允许快速查询祖先，
// 比如一个区块是否主导另一个区块。
type SparseTree []SparseTreeNode

// newSparseTree从块到父映射（按block.ID索引的数组）创建稀疏树
func newSparseTree(f *Func, parentOf []*Block) SparseTree {
	t := make(SparseTree, f.NumBlocks())
	for _, b := range f.Blocks {
		n := &t[b.ID]
		if p := parentOf[b.ID]; p != nil {
			n.parent = p
			n.sibling = t[p.ID].child
			t[p.ID].child = b
		}
	}
	t.numberBlock(f.Entry, 1)
	return t
}

// newSparseOrderedTree从块到父映射（按block.ID索引的数组）创建SparseTree
// 孩子们将以相反的顺序出现在reverseOrder中
// 特别是，如果reverseOrder是dfs ReverseStorder，则根目录将指向子目录
// 这棵树的行走将产生一个预先的命令。
func newSparseOrderedTree(f *Func, parentOf, reverseOrder []*Block) SparseTree {
	t := make(SparseTree, f.NumBlocks())
	for _, b := range reverseOrder {
		n := &t[b.ID]
		if p := parentOf[b.ID]; p != nil {
			n.parent = p
			n.sibling = t[p.ID].child
			t[p.ID].child = b
		}
	}
	t.numberBlock(f.Entry, 1)
	return t
}

// treestructure提供支配者的字符串描述
// b区和其所在的所有区的树和流结构
// 支配。
func (t SparseTree) treestructure(b *Block) string {
	return t.treestructure1(b, 0)
}
func (t SparseTree) treestructure1(b *Block, i int) string {
	s := "\n" + strings.Repeat("\t", i) + b.String() + "->["
	for i, e := range b.Succs {
		if i > 0 {
			s += ","
		}
		s += e.b.String()
	}
	s += "]"
	if c0 := t[b.ID].child; c0 != nil {
		s += "("
		for c := c0; c != nil; c = t[c.ID].sibling {
			if c != c0 {
				s += " "
			}
			s += t.treestructure1(c, i+1)
		}
		s += ")"
	}
	return s
}

// numberBlock为b和b分配入口和出口号码
// 顺序中的儿童从一个大开口序列中行走，其中n
// 是尚未分配或保留的第一个号码。N应该
// 大于零。对于每个入口和出口编号
// 保留一个大一个小的值以指示
// “严格高于”和“严格低于”。numberBlock返回
// 尚未分配或保留的最小数字（即
// 最后访问的街区的出口编号，加上两个，因为
// 最后。退出+1是保留值。）
// None
// 示例：
// None
// 单节点树根，n=1调用
// 入口=2根出口=5；返回7
// None
// 双节点树，根->子节点，n=1调用
// 入口=2根出口=11；返回13
// 入口=5子出口=8
// None
// 三节点树，根->（左，右），n=1调用
// 入口=2根出口=17；返回19
// 入口=5左出口=8；入口=11右出口=14
// None
// 这是分配和保留编号的顺序
// 最后一个例子：
// 根左右根
// 1e 3 | 4 5e 6 | 7 8x 9 | 10 11e 12 | 13 14 x 15 | 16 17 x 18

func (t SparseTree) numberBlock(b *Block, n int32) int32 {
	// 为条目-1保留n，为条目分配n+1
	n++
	t[b.ID].entry = n
	// 为条目+1保留n+1，n+2是下一个可用数字
	n += 2
	for c := t[b.ID].child; c != nil; c = t[c.ID].sibling {
		n = t.numberBlock(c, n) // 保留n=下一个自由数
	}
	// 为出口-1保留n，为出口分配n+1
	n++
	t[b.ID].exit = n
	// 为出口+1保留n+1，n+2是下一个空闲号码，返回。
	return n + 2
}

// 同胞在支配树中返回x的同胞（即。，
// 具有相同直接控制项的节点）或nil（如果存在）
// 在任意但可重复的模式中没有剩余的兄弟姐妹
// 选择顺序。因为使用了子兄弟顺序
// 要在treewalk中分配入口和出口编号，请
// 数字也与此顺序一致（即。，
// 同级（x）的入口编号大于x的出口编号）。
func (t SparseTree) Sibling(x *Block) *Block {
	return t[x.ID].sibling
}

// Child返回支配树中x的子元素，或
// 如果没有，则为零。第一个孩子的选择是
// 随意但可重复的。
func (t SparseTree) Child(x *Block) *Block {
	return t[x.ID].child
}

// 父级返回支配树中x的父级，或
// 如果x是函数的条目，则为nil。
func (t SparseTree) Parent(x *Block) *Block {
	return t[x.ID].parent
}

// isAncestorEq报告x是否是y的祖先或等同于y。
func (t SparseTree) IsAncestorEq(x, y *Block) bool {
	if x == y {
		return true
	}
	xx := &t[x.ID]
	yy := &t[y.ID]
	return xx.entry <= yy.entry && yy.exit <= xx.exit
}

// isAncestor报告x是否是y的严格祖先。
func (t SparseTree) isAncestor(x, y *Block) bool {
	if x == y {
		return false
	}
	xx := &t[x.ID]
	yy := &t[y.ID]
	return xx.entry < yy.entry && yy.exit < xx.exit
}

// domorder返回一个用于面向支配者排序的值。
// 块控制不提供总排序，
// 但二阶矩具有有用的性质。
// （1） 如果domorder（x）>domorder（y），那么x并不支配y。
// （2） 如果domorder（x）<domorder（y）和domorder（y）<domorder（z）和x不支配y，
// 那么x并不支配z。
// 属性（1）表示按domorder排序的块总是首先有一个最大主块。
// 属性（2）允许提前退出对控制块的搜索。
func (t SparseTree) domorder(x *Block) int32 {
	// 这里有一个参数，即条目（x）提供了上面记录的属性。
	// None
	// 在深度优先支配树漫游中指定入口和出口值。
	// 对于所有块x和y，以下其中一项适用：
	// None
	// （x-dom-y）x支配y=>entry（x）<entry（y）<exit（y）<exit（x）
	// （y-dom-x）y支配x=>entry（y）<entry（x）<exit（x）<exit（y）
	// （x-then-y）x和y都不支配对方，x在y=>entry（x）<exit（x）<entry（y）<exit（y）之前走
	// （y-then-x）x和y都不支配对方，y走在y=>entry（y）<exit（y）<entry（x）<exit（x）之前
	// None
	// 条目（x）>条目（y）消除了案例x-dom-y。这提供了上述属性（1）。
	// None
	// 对于属性（2），假设条目（x）<条目（y）和条目（y）<条目（z），并且x不支配y。
	// 条目（x）<条目（y）允许使用x-dom-y和x-then-y两种情况。
	// 但根据假设，x并不支配y。所以我们有x-then-y。
	// None
	// 对于矛盾，假设x支配z。
	// 然后进入（x）<进入（z）<退出（z）<退出（x）。
	// 但是我们知道x-then-y，所以入口（x）<exit（x）<entry（y）<exit（y）。
	// 结合这些，入口（x）<入口（z）<出口（z）<出口（x）<入口（y）<出口（y）。
	// 通过假设，entry（y）<entry（z），它允许y-dom-z和y-then-z的情况。
	// y-dom-z需要entry（y）<entry（z），但我们有entry（z）<entry（y）。
	// y-then-z需要出口（y）<入口（z），但我们有入口（z）<出口（y）。
	// 我们有一个矛盾，所以x不能按要求支配z。
	return t[x.ID].entry
}
